package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code92MinimumPathSun {

    public int minPathSum(int[][] grid) {
//        return process(grid, 0, 0, grid.length - 1, grid[0].length - 1);
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[m - 1][n - 1] = grid[m - 1][n - 1];
        // 右边界
        for (int i = m - 2; i >= 0; i--) {
            dp[i][n - 1] = dp[i + 1][n - 1] + grid[i][n - 1];
        }
        // 下边界
        for (int i = n - 2; i >= 0; i--) {
            dp[m - 1][i] = dp[m - 1][i + 1] + grid[m - 1][i];
        }
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) + grid[i][j];
            }
        }
        return dp[0][0];
    }

    public int process(int[][] grid, int i, int j, int m, int n) {
        if (i == m && j == n) {
            // 走到了右下角
            return grid[i][j];
        }
        // 右边界只能向下
        if (j == n) {
            return grid[i][j] + process(grid, i + 1, j, m, n);
        }
        // 下边界只能向右
        if (i == m) {
            return grid[i][j] + process(grid, i, j + 1, m, n);
        }
        // 向下或向右中的小值
        return grid[i][j] + Math.min(process(grid, i + 1, j, m, n), process(grid, i, j + 1, m, n));
    }
}
